# LeetCode 643、子数组最大平均数 I
# 一、题目描述
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
示例 1：
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
示例 2：
输入：nums = [5], k = 1
输出：5.00000
提示：
n == nums.length1 <= k <= n <= 10^5-10^4 <= nums[i] <= 10^4
# 二、题目解析
很经典的滑动窗口的题目。
具体操作如下：
1、定义需要维护的变量，即元素和、最大平均数。
2、定义窗口的首尾端 (start, end)， 然后滑动窗口。
3、窗口的右端位置从 0 开始，可以一直移动到尾部。
4、更新需要维护的变量，维护元素和的值，窗口右端新增一个元素进来，元素和发生变化。
5、如果窗口的长度为 k，需要计算平均数。
6、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度，如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变。
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 子数组最大平均数 I（LeetCode 643）：https://leetcode.cn/problems/maximum-average-subarray-i/
class Solution {
public double findMaxAverage(int[] nums, int k) {
// 滑动窗口模板化解题，五步走策略
// 【1、定义需要维护的变量】
// 对于此题来说，需要维护当前滑动窗口的元素和、滑动过程中得出的最大平均数
// 一开始，滑动窗口没有元素，元素和为 0
double sums = 0;
// 由于数组存在负数，所以 largest 设置为一个最小值
double largest = Integer.MIN_VALUE;
// 【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
// 窗口的左端位置从 0 开始
int start = 0;
// 窗口的右端位置从 0 开始，可以一直移动到尾部
for( int end = 0 ; end < nums.length ; end++ ){
// 【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
// 维护元素和的值，窗口右端新增一个元素进来，元素和发生变化
sums += nums[end];
// if 语句
// 如果窗口的长度为 k，需要计算平均数
if( end - start + 1 == k ){
// 维护 largest 变量
largest = Math.max( largest, sums / k );
}
// 【4、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度 】
// 4.1、如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变,
if( end >= k - 1 ){
// 4.2、更新 (部分或所有) 维护变量
sums -= nums[start];
// 4.3、窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变
start++;
}
}
// 【5、返回所需要的答案】
return largest;
}
}
# 2、C++ 代码
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
// 滑动窗口模板化解题，五步走策略
// 【1、定义需要维护的变量】
// 对于此题来说，需要维护当前滑动窗口的元素和、滑动过程中得出的最大平均数
// 一开始，滑动窗口没有元素，元素和为 0
double sums = 0;
// 由于数组存在负数，所以 largest 设置为一个最小值
double largest = INT_MIN;
// 【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
// 窗口的左端位置从 0 开始
int start = 0;
// 窗口的右端位置从 0 开始，可以一直移动到尾部
for( int end = 0 ; end < nums.size() ; end++ ){
// 【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
// 维护元素和的值，窗口右端新增一个元素进来，元素和发生变化
sums += nums[end];
// if 语句
// 如果窗口的长度为 k，需要计算平均数
if( end - start + 1 == k ){
// 维护 largest 变量
largest = max( largest, sums / k );
}
// 【4、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度 】
// 4.1、如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变,
if( end >= k - 1 ){
// 4.2、更新 (部分或所有) 维护变量
sums -= nums[start];
// 4.3、窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变
start++;
}
}
// 【5、返回所需要的答案】
return largest;
}
};
# 3、Python 代码
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
# 滑动窗口模板化解题，五步走策略
# 【1、定义需要维护的变量】
# 对于此题来说，需要维护当前滑动窗口的元素和、滑动过程中得出的最大平均数
# 一开始，滑动窗口没有元素，元素和为 0
sums = 0
# 由于数组存在负数，所以 largest 设置为一个最小值
largest = float('-inf')
# 【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
# 窗口的左端位置从 0 开始
start = 0
# 窗口的右端位置从 0 开始，可以一直移动到尾部
for end in range(len(nums)) :
# 【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
# 维护元素和的值，窗口右端新增一个元素进来，元素和发生变化
sums += nums[end]
# if 语句
# 如果窗口的长度为 k，需要计算平均数
if end - start + 1 == k :
# 维护 largest 变量
largest = max( largest, sums / k )
# 【4、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度 】
# 4.1、如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变,
if end >= k - 1 :
# 4.2、更新 (部分或所有) 维护变量
sums -= nums[start]
# 4.3、窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变
start += 1
# 【5、返回所需要的答案】
return largest
# 四、复杂度分析
- 时间复杂度：O(n)，其中 n 是数组 nums 的长度。遍历数组一次。
- 空间复杂度：O(1）。